import java.util.HashMap;
import java.util.Map;

/**
 * LRU缓存设计
 * LRU 定义，最近使用的放在后边（最右边），最近没用的放到前边（最左边），来了一个新的数，如果内存满了，把旧的数淘汰掉
 * 利用双链表+Hash表实现
 * 通过双链表实现新老关系排序
 * 通过Hash表示线查找
 * LinkedList+HashMap（也可以LinkedHashMap）
 */
public class LRUCache {
    //定义双向链表
    static class ListNode{
        int key;
        int val;
        ListNode pre;
        ListNode next;
        public ListNode(int key, int val){
            this.key = key;
            this.val = val;
            pre = null;
            next = null;
        }

    }
    //定义缓存中的属性
    private Map<Integer,ListNode> map;
    private int capcity;
    private ListNode head;
    private ListNode tail;

    //初始化LRUCache
    public LRUCache(int capcity){
        this.capcity = capcity;
        map = new HashMap<>();
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.pre = head;
    }
    //实现缓存数据的查询
    public int get(int key){
        //判断key是否存在
        if(!map.containsKey(key)){
            return -1;
        }
        //取值
        ListNode node = map.get(key);
        //先删除该节点，再移动该节点至链表尾部
        node.pre.next = node.next;
        node.next.pre = node.pre;
        moveNodeToTail(node);
        return node.val;
    }

    //实现缓存数据的插入
    public void put(int key, int val){
        //判断key是否存在
        if(map.containsKey(key)){
            //如果存在，更改值，并将node移动至链表尾部
            map.get(key).val = val;
            return;
        }
        //如果不存在,新增节点，并将节点加入尾部，如果超出容量，把头结点删掉
        ListNode node = new ListNode(key, val);
        map.put(key, node);
        moveNodeToTail(node);
        //判断是否超出缓存容量
        if(map.size() > capcity){
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.pre = head;
        }
    }

    //辅助函数，实现将缓存数据中节点数据移动至链表尾部
    public void moveNodeToTail(ListNode node){
        node.next = tail;
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
    }


    public static void main(String[] args) {
        LRUCache lc = new LRUCache(2);
        lc.put(1, 1);
        lc.put(2, 2);
        lc.put(3, 3);
        int i = lc.get(1);
        System.out.println(i);
        System.out.println(lc.get(3));
        System.out.println(lc.get(2));
        lc.put(4,4);
        System.out.println(lc.get(3));
        System.out.println(lc.get(2));
    }
}
